\chapter{Introducci\'on}

\section{Conceptos B\'asicos}

\paragraph{}
Dado que en computaci\'on y matem\'aticas es muy com\'un el uso de tecnicismos, es primordial que el lector est\'e familiarizado con los mismos. En esta secci\'on se definir\'an los principales conceptos que se estar\'an usando a lo largo de la t\'esis.

\subsection{Estructura de Datos}

\paragraph{}
Una estructura de datos es un medio de almacenamiento de datos en una computadora de manera que los datos puedan ser accesados de manera r\'apida y eficiente. Cuando es bien dise\~nada, una estructura de datos suele permitir diferentes operaciones usando pocos recursos en tiempo de ejecuci\'on y espacio en memoria. En el \'area de gr\'aficos computacionales y en particular en el cargado y almacenamiento de objetos en 3D (usualmente llamados ``formatos''), una estructura de datos eficiente tiene que tener un balance en las siguientes \'areas:
\begin{enumerate}
 \item Tiempo de preproceso (cargado del objeto)
 \item Facilidad de acceso de los elementos (v\'ertices, aristas, puntos, etc.)
 \item Tiempo de almacenamiento 
 \item Facilidad de conversi\'on entre estructuras de datos diferentes.
\end{enumerate}

\subsection{Grafo}

\paragraph{}
En ciencias computacionales un grafo es una estructura de datos que consiste en un par ordenado $G := (V,E)$ en la que $V$ es un conjunto de v\'ertices (nodos) y $E$ un conjunto de aristas que representan una relaci\'on binaria entre elementos de $V$ con $V$ y $E$ finitos.

\subsection{\'Arbol}

\paragraph{}
Un \'arbol es un caso particular de un grafo el cual tiene las siguientes propiedades. Las aristas del grafo tienen direcci\'on, es decir, el conjunto de aristas se ve de la siguiente manera:
\begin{equation}
E \subseteq \{x\in\mathcal P(V):1\leq |x|\leq2\}
\end{equation}

\paragraph{}
Adem\'as de la propiedad anterior el grafo no podr\'a contener ciclos de manera que al recorrer el \'arbol no se podr\'a regresar a un nodo ya visitado. Un grafo que cumple estas propiedades es llamado un DAG\footnote{``Directed acyclic graph`` o grafo aciclico dirigido}. Se le llama nodo (o vertice) ra\'iz al nodo que no tiene ninguna arista incidente, de igual manera se le llaman hijos de alg\'un nodo a los nodos conectados por sus aristas salientes y padre al nodo del cu\'al proviene la arista incidente (si es que tiene) de alg\'un nodo.

\paragraph{}
En particular, en esta t\'esis estaremos trabajando con un h\'ibrido de un \'arbol gen\'erico con quad-trees\cite{QuadTree}. Un quad-tree es un \'arbol el cu\'al cada nodo contiene a lo m\'as 4 hijos usado mayormente para el particionamiento de espacios 2D subdividi\'endolo recursivamente en cuadrantes. 

\subsection{Axis-Alligned Bounding Boxes}
\label{aabbs}
\paragraph{}

\begin{figure}[htp]
  \begin{center}
    \subfigure[AABB]{\label{fig:AABB}\includegraphics[scale=0.7]{BB/aabb.eps}}
    \subfigure[Otras posibles fronteras]{\label{fig:otras}\includegraphics[scale=0.7]{BB/otras_fronteras.eps}} \\
  \end{center}
  \caption{Diferentes tipos de fronteras para un mismo conjunto de objetos}
  \label{fig:bounding_volumes}
\end{figure}

Dado un conjunto de objetos (ya sean puntos o pol\'igonos), un volumen frontera o ''bounding volume`` es un volumen tal que contenga a todos los objetos del conjunto. Como se muestra en la figura \ref{fig:bounding_volumes} existen diferentes tipos de volumenes frontera, cuando se habla de caja frontera o ''bounding box`` se refiere a el m\'inimo rect\'angulo (o cubo si es $\Re^3$) tal que contenga a todos los objetos del conjunto. el caso en particular en que se escogen las cajas frontera de manera que las paredes de la superficie est\'en alineadas con los ejes coordenados se les llaman cajas frontera alineadas a los ejes o ''axis-allligned bounding boxes`` (AABB's); a pesar de que no suelen ser las mejores fronteras son r\'apidas de calcular y bajo el prop\'osito del algor\'itmo propuesto ajustan perfectamente a el procedimiento.

\subsection{Coordenadas Homog\'eneas}
\label{coordenadas_homogeneas}

\paragraph{}
Dado un vector en $\Re^{3}$ podemos generar transformaciones lineales tales como escalamiento y rotaci\'on  con matrices de $3x3$ y se pueden realizar en conjunto con simples operaciones matriciales, sin embargo para generalizar las transformaciones que son necesarias para visualizar objetos en 3D, es decir, transformaciones afines, se estar\'ia dejando de lado la traslaci\'on que no puede ser expresada por una matriz de $3x3$. Para transformar un vector $\vec{v}$ de un sistema coordenado a otro usualmente se opera de la siguiente manera:
\begin{equation}
\label{translation}
	\vec{v}' = M\vec{v} + \vec{t}
\end{equation}
Donde $M$ es una matriz de tama\~no $3x3$ invertible y $\vec{t}$ un vector de translaci\'on. Al realizar dos operaciones como la realizada en la ecuaci\'on \ref{translation} el vector $\vec{v}$ quedar\'ia de la siguiente manera:
\begin{equation}
	\vec{v}' = M_2(M_1\vec{v} + \vec{t}_1) + \vec{t}_2
	= (M_2M_1)\vec{v} + M_2\vec{t}_1 + \vec{t}_2
\end{equation}
De manera que para seguir operando de esta manera se tendr\'ia que mantener en alguna variable el resultado de $M_nM_{n-1}$ as\'i como el valor de traslaci\'on $M_n\vec{t}_{n-1} + \vec{t}_n$ en cada estado cuando se concatenen translaciones lo cual no ser\'ia \'optimo ya que ser\'ia necesario guardar mas variables sin contar las m\'ultiples operaciones matriciales.

\paragraph{}
Para generar todas las transformaciones afines incluyendo la traslaci\'on se utiliz\'o un metodo el cual extiende las coordenadas en 3D a 4D usando matrices de $4x4$ y agregando una coordenada a cada punto que llamaremos $w$ y es igual a 1\footnote{Cuando se quiere hacer una transformacion sin traslaci\'on s\'olo basta con poner 0 en la coordenada $w$ para que la componente de traslaci\'on de cualquier matriz de transformaci\'on homog\'enea se elimine. En general, la coordenada $w$ se encarga de la proyecci\'on del vector de la siguiente manera $\vec{v} = (x/w,y/w,z/w)$}. Una matr\'iz de translaci\'on en coordenadas homog\'eneas se ve de la siguiente manera:
\begin{equation}
    \vec{v}' = M_h\vec{v} = 
     \begin{pmatrix}
	1&0&0&a\\
	0&1&0&b\\
	0&0&1&c\\
	0&0&0&1
     \end{pmatrix}
     \begin{pmatrix}
	x\\
	y\\
	z\\
	1
      \end{pmatrix}
      =
      \begin{pmatrix}
	x+a\\
	y+b\\
	z+c\\
	1
      \end{pmatrix}
\end{equation}
En general, todas las transformaciones lineales se pueden realizar de la misma manera que se hac\'ian en matrices de $3x3$. Sea $T$ una transformaci\'on lineal en $\Re^3$ su equivalente en coordenadas homog\'eneas $T_h$ ser\'a:
\begin{equation}
    T_h = 
    \begin{pmatrix}
     M&0\\
     0&1
    \end{pmatrix}
\end{equation}


\section{Gr\'aficos Computacionales}

\paragraph{}
Los gr\'aficos computacionales son un \'area de ciencias computacionales encargada del manejo en pantalla de la visualizaci\'on. \'Esta \'area 
a su vez se divide en sub\'areas de las cuales nos enfocaremos en la visualizaci\'on. Esta sub\'area se en carga de los procesos y algor\'itmos
necesarios para poder poner en pantalla lo que se quiere mostrar, a muy bajo nivel, es la manipulaci\'on correcta del arreglo de pixeles de la pantalla
de manera que tengamos control sobre lo que se ve en la misma.

\paragraph{}
A lo largo de la historia de la computaci\'on y desde que se empezaron a crear gr\'aficos en 3D, se han implementado diversos algor\'itmos para visualizar objetos s\'olidos. Dos de esos m\'etodos fueron los que prevalecieron hasta hoy en d\'ia, la rasterizaci\'on y el ``Ray tracing'' (rastreado de rayos). La rasterizaci\'on fue optada por los fabricantes de tarjetas de video ya que era el m\'etodo m\'as \'optimo hasta el momento para visualizaci\'on en tiempo real. El ``Ray Tracing'' por el contrario es mucho m\'as lento pero puede obtener resultados m\'as fotorealistas, por lo que se opt\'o para creaci\'on de animaciones ``off-line``(no en tiempo real). No fue sino hasta finales de los 90's que la capacidad computacional ya no estaba al d\'ia con las exigencias de visualizaci\'on, en particular con objetos de topolog\'ia compleja. Esto di\'o pi\'e a la b\'usqueda de nuevos procedimientos para optimizar la visualizaci\'on, uno de estos m\'etodos que surgi\'o fue el renderizado a base de puntos.

\subsection{Renderizaci\'on}

\paragraph{}
El t\'ermino renderizaci\'on proviene de la palabra en ingl\'es ``render'' la cu\'al no tiene un t\'ermino semejante en espa\~nol por la que se suele utilizar el t\'ermino renderizaci\'on o rendereado. Es el proceso de generar una imagen a partir de un objeto, en general, es el proceso de generar una imagen 2D a partir de una escena 3D haciendo una proyecci\'on desde el punto de vista de la c\'amara hacia el mundo con determinados par\'ametros prestablecidos tales como el FOV\footnote{FOV se traduce como campo de visi\'on ``Field of view'' el cu\'al es el \'angulo que representa la apertura de la c\'amara en el eje Y}, Aspect-ratio\footnote{Aspect Ratio es la raz\'on del $\frac{ancho}{alto}$ de la c\'amara}, al igual que otros par\'amatros de optimizaci\'on para descartar el renderizado de objetos detr\'as de la c\'amara o muy lejos.

\paragraph{}
As\'i mismo, la renderizaci\'on se divide en dos corrientes principales las cuales son objeto de investigaci\'on de manera independiente y aunque comparten algunos algor\'itmos, su implementaci\'on es completamente diferente dada la naturaleza de cada vertiente. El renderizado off-line (fuera de linea) es utilizado principalmente en producci\'on de pel\'iculas y arquitectura ya que puede alcanzar niveles de realismo muy altos. Una renderizaci\'on off-line puede tardar desde mil\'esimas de segundo, hasta horas, dependiendo de la cantidad de objetos, t\'ecnicas y efectos utilizados tales como iluminaci\'on global, blur (emborronamiento), motion-blur (emborronamiento debido al movimiento), etc. La segunda corriente es la renderizaci\'on en tiempo real la cu\'al ser\'a estudiada a lo largo de esta t\'esis, comunmente encontrada en video juegos, visuializaci\'on cient\'ifica y m\'edica, haptics y realidad virtual. El principal reto de la renderizaci\'on en tiempo real es la optimizaci\'on necesaria para poder mantener un rendimiento de cuadros por segundo tal que la transici\'on de los cuadros sea lo suficientemente fluida para ser imperceptible para el ojo humano\footnote{Generalmente a partir de 24 cuadros por segundo aunque la mayor\'ia de las aplicaci\'ones procuran un rendimiento de 60 cuadros por segundo}. Este es un trabajo particularmente dif\'icil hoy en d\'ia por la demanda de realismo en las aplicaciones y las limitaciones de hardware.

\subsection{Rasterizaci\'on}

\paragraph{}
La rasterizaci\'on es el principal m\'etodo de renderizaci\'on en tiempo real por su rapidez y rendimiento, ya que est\'a implementada en hardware en conjunto con dos t\'ecinas m\'as que conforman el proceso de renderizado(eliminaci\'on de superficies ocultas y sombreado de pixeles), que por simplicidad englobaremos en el t\'ermino rasterizaci\'on. Por lo que fue el m\'etodo utilizado para comparar la estructura de datos propuesta en esta t\'esis.

\paragraph{}
Dado un pol\'igono de $n$ lados en 3D(usualmente tri\'angulos) el proceso de rasterizaci\'on consiste en una proyecci\'on del pol\'igono en el espacio de coordenadas de la pantalla. A pesar de que parece una tarea f\'acil, hay que tener particular cuidado en que los pol\'igonos adyacentes embonen y que no queden agujeros. El m\'etodo consiste en obtener la proyecci\'on de los v\'ertices del pol\'igono al espacio de la pantalla y rasterizar los lados encontrando los pixeles m\'as cercanos al lado con alg\'un algor\'irmo tal como Bresenham\cite{Bresenham} o un DDA (Analizador diferencial digital)\cite{DDA64} tal como muestra el siguiente pseudo c\'odigo:

\paragraph{}
Sea $(xs,ys), (xe,ye)$ los extremos del lado a rasterizar,
\begin{algorithmic}
	\STATE $x=xs$
	\STATE $m=(xe-xs)/(ye-ys)$
	\FOR{$y=ys$ to $ye$}
	\STATE	$resultado(redondeo(x),y)$
	\STATE	$x=x+m$
	\ENDFOR
\end{algorithmic}
El problema principal es la repetitiva conversi\'on de $m$ y $x$ real-entero y vice-versa\cite{ComputerImage}.

\paragraph{}
Una vez rasterizados los lados del pol\'igono s\'olo resta rellenarlo, lo cu\'al requiere especial cuidado, como se mencion\'o anteriormente, para no dejar huecos en el objeto. El algor\'itmo usado para este proceso es llamado ``scan-line rendering''; y consiste en ordenar los lados del pol\'igono por m\'inimo valor en el eje ``y'' (usualmente bucket sort) y llenar el pol\'igono progresivamente l\'inea por l\'inea del arreglo de pixeles en orden ascendente. Es importante notar que este proceso a\'un carece de sombreado o de color alguno, esto se genera posteriormente donde los algor\'itmos principales de sombreado son gourand y phong shading\footnote{Adem\'as de las posibilidades de crear scripts personalizados usando la librer\'ia de sombreado de OpenGL (Shader Library)}.

\subsection{Renderizaci\'on a Base de Puntos}
\label{PBR}

\paragraph{}
Como se vi\'o anteriormente, la rasterizaci\'on es un m\'etodo que est\'a basado en superficies poligonales, en particular tri\'angulos, para la visualizaci\'on de objetos en 3D, los cuales son colocados de manera que juntos generan un objeto m\'as complejo. La renderizaci\'on a base de puntos es un nuevo paradigma que en vez de tomar como geometr\'ia base el tri\'angulo, usa splats. Un splat est\'a conformado por una posici\'on, y dependiendo del sistema de visualizaci\'on puede tener otras propiedades tales como un radio o dos radios, dependiendo si el splat ser\'a representado por una superficie circular o el\'iptica. Uno de los principales modelos de renderizaci\'on es  "QSplat: A Multiresolution Point Rendering System for Large Meshes" por Szymon Rusinkiewicz et al, el cual es la base del algor\'itmo presentado en esta t\'esis.

\paragraph{}
Los objetos ahora son compuestos por un conjunto de puntos, y el radio de cada splat debe ser computado de tal manera que el objeto parezca s\'olido, es decir, que no tenga huecos entre los puntos. El primer problema que podemos observar es que la mayor\'ia de modelos en 3D est\'an compuestos con pol\'igonos y para poder aplicar un algor\'itmo de renderizado a base de puntos, es necesaria la conversi\'on de pol\'igonos a splats. Esta conversi\'on en s\'i misma, es un \'area de investigaci\'on. En esta t\'esis se presenta entre otras cosas un nuevo algor\'itmo para la conversi\'on del objeto.

\subsection{Frustum-Culling}
\label{frustum_culling}

\paragraph{}
Frustum-culling es un m\'etodo de optimizaci\'on el cual sirve para descartar el renderizado de objetos que se encuentren fuera del campo de visi\'on de la c\'amara (frustum). Para entender el m\'etodo es importante entender el campo de visi\'on de una c\'amara de OpenGL y como generar este ``view frustum''.

\paragraph{}
El ``view frustum'' es el volumen del espacio que contiene todo lo que ser\'a visible en una escena 3D. Para proyecciones perspectivas (que ser\'a nuestro caso) este volumen tiene forma de piramide con base cuadrangular cuyo v\'ertice superior es la posici\'on de la c\'amara como se muestra en la figura \ref{fig:view_frustum}. El ``view frustum'' est\'a delimitado por seis planos de los cuales nos preocuparemos por los 4 que conforman las paredes de la piramide\footnote{Los dos planos restantes son el plano \textit{cerca} y el \textit{lejos} y el proceso de descartar geometria fuera de ellos est\'a incoroprada en OpenGL nativamente por lo que no es de relevancia.}. La distancia entre el plano \textit{cerca} y la c\'amara es lo que se traducir\'a como punto focal de la misma. Es importante notar que la distancia del punto focal a sus extremos en el eje $x$ es 1 de manera que para ajustar la raz\'on de proporci\'on del ``view frustum'' se deber\'a ajustar la altura del campo modificando as\'i el \'angulo que genera con la vertical el cual es llamado FOV o ``field of vision'' que significa campo de visi\'on.

\begin{figure}
 \centering
 \includegraphics[scale=0.7]{frustum_culling.eps}
 % frustum_culling.eps: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=14 14 358 254
 \caption{Donde $f$ es el punto focal y \textit{cerca} y \textit{lejos} planos del ``view frustum''. Como se puede observar, usando el proseso de frustum-culling el objeto A no ser\'a renderizado a diferencia del objeto B el cual est\'a dento del volumen.}
 \label{fig:view_frustum}
\end{figure}


\paragraph{}
El proceso de frustum-culling consiste en realizar pruebas a los 6 planos que generan el volumen del ``view-frustum'' de manera que se pueda descartar los objetos que se encuentran fuera el mismo. Ya que en principio es una operaci\'on costosa, este proceso suele ser realizado por conjuntos de pol\'igonos y no por cada pol\'igono en un objeto. El m\'etodo de agrupaci\'on depende de la implementaci\'on y como se ver\'a mas adelante, para el m\'etodo propuesto fueron utilizados AABB's.

\subsection{Ray Casting}
\label{ray_casting}

\begin{figure}
 \centering
 \includegraphics[bb=14 14 299 135]{ray_casting.eps}
 % ray_casting.eps: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=14 14 299 135
 \label{fig:ray_casting}
 \caption{Ray casting}
\end{figure}

\paragraph{}
El algor\'itmo de ray casting fue uno de los primeros algor\'itmos creados para renderizaci\'on en 3D el cual fue implementado en los primeros juegos que introdujeron la tercera dimensi\'on tal como lo fue Wolfenstein3D. Este algor\'itmo consiste en generar un rayo desde la posici\'on de la c\'amara hacia cada pixel y encontrar su intersecci\'on con los objetos de una escena quedandose as\'i con el m\'as cercano y guardando su color para el renderizado.

\begin{algorithmic}
	\FOR{cada pixel en la pantalla}
		\STATE construir rayo desde la c\'amara al pixel
		\FOR{cada objeto en la escena}
			\STATE buscar intersecci\'on y almacenar la m\'as cercana
		\ENDFOR
	\ENDFOR
\end{algorithmic}

Y siguiendo la figura \ref{fig:ray_casting} la ecuaci\'on del vector que representa el rayo que parte de la c\'amara a un pixel $(i,j)$ est\'a dada de la siguiente manera:

\begin{equation}
 \vec{r} = \vec{p} + focal*\vec{d} + (i-\frac{w}{2})\vec{x_a} + (\frac{w}{2}-j)\vec{y_a}
\end{equation}

Donde $p$ y $d$ son la posici\'on y direcci\'on de la c\'amara respectivamente, $focal$ el punto focal de la c\'amara, $w$ y $h$ el ancho y alto de la pantalla (en pixeles) y $x_a$ y $y_a$ los ejes coordenados relativos a la c\'amara que delimitan su orientaci\'on.

\section{Motivaci\'on y Contribuci\'on}

\paragraph{}
Como se ha mencionado anteriormente, los tri\'angulos han sido los primitivos predilectos para renderizaci\'on de objetos. No fue sino hasta 1985 donde Levoy y Whitted introdujeron la noci\'on de puntos como primitivos para visualizar objetos en \cite{LW85} donde a pesar de que el algor\'itmo propuesto realizaba muchos c\'alculos por punto, di\'o pie a nuevas t\'ecnias como la propuesta por Grossman y Dally en \cite{GD98} usando un algor\'itmo de sampleo uniforme de puntos. 

\paragraph{}
A pesar de la preferencia por primitivos poligonales, los puntos son la manera natural de representar ciertos fen\'omenos tales como visualizaci\'on cient\'ifica, y para nuestro caso en particular, escaneo de objetos en 3D, por lo que el uso de puntos como primitivo de renderizado a ganado popularidad recientemente como una representaci\'on alternativa de la geometr\'ia, eficiente para el renderizado y altamente flexible para manipulaci\'on de objetos 3D altamente complejos. QSplat\cite{RL00}, es un algor\'itmo que fue presentado en el a\~no 2000 por Rusinkiewicz y Levoy el cu\'al fue dise\~nado para visualizar cuerpos geom\'etricos de alta definici\'on en tiempo real.

\paragraph{}
Es de vital importancia notar que los m\'etodos de renderizaci\'on a base de puntos no son una alternativa viable a la visualizaci\'on tradicional en t\'erminos generales. El uso de puntos como primitivos comienza a cobrar importancia cuando el n\'umero de tri\'angulos que componen a un objeto son muy grandes y que adem\'as al visualizar el objeto los tri\'angulos sean del orden de un pixel. Esta regla se cumple para muchos casos tales como renderizado de objetos org\'anicos o de superficies con topolog\'ias complejas que en conjunto con la continua b\'usqueda del realismo en los gr\'aficos computacionales y el hardware existente, exigen mayor definici\'on y realismo. Por este hecho, el campo de investigaci\'on del renderizadoa base de puntos a crecido r\'apidamente en los \'ultimos a\~nos donde se ha empezado a pensar en m\'etodos h\'ibridos\cite{HybridPBR} de renderizaci\'on usando puntos y tri\'angulos como primitivos para las diferentes necesidades en una misma escena. Varios ejemplos de estos m\'etodos pueden encontrarse en video juegos de automovilismo donde objetos tales como \'arboles o espectadores en el horizonte van creciendo a medida que el carro se acerca a ellos modificando as\'i su topolog\'ia para ahorrar recursos de renderizado y mantener un rendimiento consistente.

\paragraph{}
Una vez entendida la importancia del renderizado a base de puntos, en esta t\'esis se muestra un nuevo m\'etodo para optimizar la visualizaci\'on de
modelos de alta definici\'on. Este m\'etodo engloba todo el proceso desde la conversi\'on de objetos poligonales hasta el renderizado, y se prob\'o que vale la pena continuar la investigaci\'on del mismo ya que presenta mejoras en rendimiento al m\'etodo tradicional de renderizaci\'on.


\section{Estado del Arte}
\label{estado_del_arte}

\paragraph{}
El \'area de renderizado a base de puntos a evolucionado mucho en los \'ultimos a\~nos en los cuales un alg\'oritmos a prevalecido siendo la base para los nuevos m\'etodos. El principal problema del renderizado a base de puntos es su dificultad de hacer comparaciones entre diferentes algor\'itmos ya que suelen ser muy especializados para alguna representaci\'on. Este algor\'itmo es el QSplat\cite{RL00} desarrollado en el a\~no 2000 por Szymon Rusinkiewicz y Marc Levoy de la universidad de Stanford siendo base para algor\'itmos posteriores como el SPT\cite{SPT} y POP\cite{HybridPBR} entre otros.

\subsection{QSplat}

\paragraph{}
QSplat es un producto del desarrollo de un proyecto llamado ``Digital Michellangelo Project'' el cual ten\'ia como prop\'osito digitalizar esculturas antiguas entre las que se encuentra el David, San Mateo, etc. Debido a la gran cantidad de datos extraidos al digitalizar las esculturas, se comenz\'o a desarrollar un m\'etodo para visualizar objetos con una cantidad de pol\'igonos del orden de cientos de mill\'ones de pol\'igonos en tiempo real que posteriormente fue denominado ``QSplat''. El algor\'itmo ten\'ia que cumplir las siguientes expectativas:
\begin{itemize}
 \item R\'apido para inicializar y cargado de modelo progresivo.
 \item Interactividad en tiempo real.
 \item Una estructura de datos con multi-resoluci\'on para renderizar a base de puntos.
 \item Con una representasi\'on compacta (compresi\'on).
 \item Rapid\'ez de preproceso.
\end{itemize}

El algor\'itmo cubri\'o las expectativas y fue implementado en un software que actualmente se encuentra como exposici\'on permanente en diversos museos y capillas en Florencia, Italia.

\subsubsection{Algor\'itmo de Preproceso}
\paragraph{}
Ya que este algor\'itmo parte de un mesh a base de tri\'angulos se generan esferas frontera ``bounding spheres'' por cada v\'ertice del tama\~no de la esfera de frontera mayor de los v\'ertices conectados a el garantizando as\'i que el objeto no tenga hoyos entre los splats. Una vez obtenido el radio de cada esfera se utiliza el siguiente algor\'itmo para construir el resto del \'arbol:

\begin{algorithm}
\caption{ConstruirArbol(vertices[inicio..final])}
\begin{algorithmic}
	\IF{inicio == final}
		\RETURN Esfera(vertices[inicio])
	\ELSE
		\STATE puntomedio = ParticionarPorEjeMasLargo(vertices[inicio..fin])
		\STATE subarbolizquierdo = ConstruirArbol(vertices[inicio..puntomedio])
		\STATE subarbolderecho = ConstruirArbol(vertices[puntomedio+1..fin])
		\RETURN EsferaFrontera(subarbolizquierdo, subarbolderecho)
	\ENDIF
\end{algorithmic}
\end{algorithm}

Donde el algor\'itmo se genera particionando el conjunto de v\'ertices por el eje m\'as largo y generando sub\'arboles recursivamente. Cuando la recursi\'on llega a un s\'olo punto, s\'olo se genera una esfera. Los atributos como la posici\'on, normal y color son promediados en cada nivel del sub\'arbol y son usados como se ver\'a a continuaci\'on.


\subsubsection{Algor\'itmo de Renderizado}
\paragraph{}
Una vez generado el \'arbol de multi-resoluci\'on s\'olo basta usar el algor\'itmo \ref{renderizado_qsplat} para el renderizado en el cual se generan tambi\'en las pruebas de visibilidad y de rendimiento para descartar ramas completas del \'arbol.
\begin{algorithm}
 \caption{RecorrerArbol(nodo)}
 \label{renderizado_qsplat}
 \begin{algorithmic}
	\IF{el nodo no esta en el campo de visi\'on}
		\STATE no recorrer esta rama del \'arbol
	\ELSE
		\IF{el nodo es hoja del \'arbol}
			\STATE dibujar splat
		\ELSE
			\IF{no vale la pena continuar la recursi\'on}
				\STATE dibujar splat
			\ELSE
				\FOR{cada hijo del nodo}
					\STATE RecorrerArbol(hijo)
				\ENDFOR
			\ENDIF
		\ENDIF
	\ENDIF
 \end{algorithmic}
\end{algorithm}
\paragraph{}
Se recorre recursivamente el \'arbol y cuando encuentra una hoja se dibuja el splat. Tambi\'en, si la heur\'istica implementada decide que no vale la pena hacer la recursi\'on por problemas de rendimiento tambi\'en dibuja el splat y no continua el recorrido del \'arbol. De otra manera, recorre recursivamente los hijos del nodo.






